package com.whitedust.top40;

/**
 * @author A
 * @since 2025/11/5 10:36
 */

public class Top38 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //无论奇偶都能适用，奇数则left==right
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, m - 1, nums2, 0, n - 1, left)
                + findKth(nums1, 0, m - 1, nums2, 0, n - 1, right)) * 0.5;
    }

    public int findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //确保nums1一定是更短的数组
        if (len1 > len2) return findKth(nums2, start2, end2, nums1, start1, end1, k);
        //一定要判断len1为0的情况，不然下面计算后访问会越界
        if (len1 == 0) return nums2[start2 + k - 1];
        //返回的应该是开始传入的开始位置而不是0
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);
        //找出两个数组中的前k/2个数
        //当k/2比数组允许访问的长度长的时候就只能访问到最末端了
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;
        //当第一个数组的第k/2个数大于第二个数组的k/2个数，意味着第二个数组的k/2个数肯定都不是第k小的数。
        //相当于每进行一次排除k/2个数，直到一方为空，或者是k==1,即两数组中最小的数。
        if (nums1[i] > nums2[j]) {
            return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}
